# -*- coding: utf-8 -*-

"""剑指 Offer II 048. 序列化与反序列化二叉树
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[1,2]

提示：
输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，也可以采用其他的方法解决这个问题。
树中结点数在范围 [0, 10^4] 内
-1000 <= Node.val <= 1000"""


from queue import LifoQueue, Empty

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Mount(object):
    """记录 TreeNode 哪个枝丫接受挂载 left/right """
    def __init__(self, treeNode, accept):
        self.treeNode = treeNode
        self.accept = accept


class Codec:
    """前面几道题都用到了层遍历，这到题用深度遍历看看，采用中序遍历，那么相对应的任务队列应该用栈。
    这里没有采用递归的方式，因为不是完全二叉树，树中节点数不大于10000个，有可能深度大于1000，递归造成栈溢出。
    
    提交的时候，谜之异常，需要注释掉 TreeNode ，前面那些题都不需要注释掉。"""
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        data = []
        if root:
            stack = LifoQueue()
            stack.put(root)
            while True:
                try:
                    treeNode = stack.get_nowait()
                    if treeNode:
                        data.append(treeNode.val)
                        stack.put(treeNode.right)
                        stack.put(treeNode.left)
                    else:
                        data.append(None)
                except Empty:
                    break
        return str(data)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        stack = LifoQueue()
        data = data[1:-1]
        data = data.split(',')
        vals = []
        for d in data:
            try:
                vals.append(int(d))
            except ValueError:
                vals.append(None)

        gurd = TreeNode(0)
        gurd.left = TreeNode(0)
        stack.put(Mount(gurd, 'R'))
        for val in vals:
            mount = stack.get_nowait()
            parent = mount.treeNode

            if val is not None:
                treeNode = TreeNode(val)
                stack.put(Mount(treeNode, 'R'))
                stack.put(Mount(treeNode, 'L'))
            else:
                treeNode = None

            if mount.accept == 'L':
                parent.left = treeNode
            elif mount.accept == 'R':
                parent.right = treeNode

        return gurd.right

    def show_tree(self, root):
        def printf(node, form):
            print("%s%s" % (form, node.val))
            if node.left:
                printf(node.left, form+'    ')
            if node.right:
                printf(node.right, form+'    ')
        printf(root, '')


# Your Codec object will be instantiated and called as such:
ser = Codec()
deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
data = '[1, 2, 6, None, None, None, 3, 4, None, None,5, None, None]'
# data = '[1,]'
# data = '[]'
tree = deser.deserialize(data)
deser.show_tree(tree)
# print(tree)
data = ser.serialize(tree)
print(data)
